#include <iostream>

void MaxHeap(int*a,int n,int i)
{
    int left = 2*i + 1;
    int right = 2*i + 2;

    int maxIndex = i;
    if(left < n&&a[left] > a[i])
    {
        maxIndex = left;
    }

    if(right < n&&a[right] > a[maxIndex])
    {
        maxIndex = right;
    }

    if(maxIndex != i)
    {
        std::swap(a[i],a[maxIndex]);
        MaxHeap(a,n,maxIndex);
    }
}

void HeapSort(int *a,int n)
{   
    //第一个非叶子节点
    for(int i = n/2 - 1;i >= 0;i--)
    {
        MaxHeap(a,n,i);
    }

    for(int i = n-1;i >= 0;i--)
    {
        std::swap(a[0],a[i]);
        MaxHeap(a,i,0);
    }
   
}
int main()
{   
    int a[] = {5,2,1,1,4,6,3,8,2};
    HeapSort(a,sizeof(a)/sizeof(a[0]));
    for(int i = 0;i < sizeof(a)/sizeof(a[0]);i++)
    {
        std::cout<<a[i]<<" ";
    }
        std::cout<<std::endl;
    return 0;
}